import random
import time
from typing import List, Tuple, Any, Optional

import h3
import numpy as np

from myapp.pp_py.src.config.config import PPConfig
from myapp.pp_py.src.data_structures.base_structures import Map, HexCell
from myapp.pp_py.src.pp.pp_engine import PPEngine
from myapp.pp_py.src.utils.map_converter import load_map


class GeneticPathFinder:
    def __init__(self,
                 map: Map, # 地图对象
                 start_index: Any, # 起点索引
                 end_index: Any,  # 终点索引
                 population_size: int = 100, # 种群大小
                 max_generations: int = 500, # 最大迭代代数
                 mutation_rate: float = 0.1, # 变异概率
                 top_paths_count: int = 3): # 要追踪和显示的最优路径数量
        self.top_paths = None # 最优的前几条路径
        self.map = map
        self.start_index = start_index
        self.end_index = end_index
        self.population_size = population_size
        self.max_generations = max_generations
        self.mutation_rate = mutation_rate
        self.top_paths_count = top_paths_count  # 新增参数，控制追踪的路径数量
        # 验证起点和终点是否有效
        if start_index not in map.cells or end_index not in map.cells:
            raise ValueError("起点或终点不在地图范围内")
        start_cell = map.cells[start_index]
        end_cell = map.cells[end_index]
        # 判断起终点是否可达
        if PPEngine.reject_cell(start_cell) or PPEngine.reject_cell(end_cell):
            # 清空模块
            PPEngine.pp_engine_components.clear()
            raise ValueError("起点或终点不可达")

    # 获取位置权重
    def _get_position_weight(self, current_index: Any) -> int:
        return 1

    # 生成偏向终点的随机路径
    def _generate_random_path(self) -> List[Any]:
        path = [self.start_index] # 初始化路径
        current_index = self.start_index
        max_steps = h3.h3_line(self.start_index,self.end_index).length()*3 # 最大步数
        steps = 0
        # 生成初始种群，每个个体直到终点或者最大步数，生成路径
        while current_index != self.end_index and steps < max_steps:
            neighbors_indexes = self._get_neighbors_indexes(current_index, path)
            # 无路可走了，退回上一步，然后continue
            if not neighbors_indexes:
                if len(path) > 1:
                    path.pop()
                    current_index = path[-1]
                else:
                    break
                continue
            # 偏向选择靠近终点的方向
            best_neighbor_index = None # 最佳邻居索引
            best_distance = float('inf') # 最小距离
            # 更新最佳邻居与最佳距离
            for neighbor_index in neighbors_indexes:
                distance = h3.h3_distance(neighbor_index,self.end_index)
                if distance < best_distance:
                    best_distance = distance
                    best_neighbor_index = neighbor_index
            # 80%概率选择最佳方向，20%随机选择
            if random.random() < 0.8 and best_neighbor_index:
                current_index = best_neighbor_index
            else:
                current_index = random.choice(neighbors_indexes)
            # 添加当前位置到路径点集中
            path.append(current_index)
            steps += 1
        return path

    # 获取当前位置的邻居，若邻居不在map中会被剔除
    def _get_neighbors_indexes(self, current_index: Any, path: List[Any]) -> List[Any]:
        neighbors_indexes = []
        temp = h3.k_ring(current_index, 1)  # 获取邻接cell的h3索引
        temp.discard(current_index)  # 移除自身索引
        for index in temp:
            if index not in path and index in self.map.cells:
                neighbors_indexes.append(index)
        return neighbors_indexes

    def calculate_path_cost(self, path: List[Tuple[int, int]]) -> float:
        """计算路径总成本（权重和）"""
        if not path:
            return float('inf')

        path_total_cost = 0
        for index in path:
            path_total_cost += self._get_position_weight(index)
        return path_total_cost
吗
    def _calculate_fitness(self, path: List[Any]) -> float:
        """计算适应度"""
        if not path or path[0] != self.start_index:
            return 0

        # 如果路径到达终点，给予高奖励
        if path[-1] == self.end_index:
            cost = self.calculate_path_cost(path)
            # 到达终点的路径应该获得比任何未到达路径更高的适应度
            base_reward = 1000  # 基础奖励
            return base_reward / (cost + 1)

        # 对于未到达终点的路径，主要奖励距离终点的接近程度
        last_index = path[-1]
        manhattan_distance = h3.h3_distance(last_index, self.end_index)

        # 减少对路径长度和成本的惩罚，重点奖励接近终点
        return 1.0 / (manhattan_distance + 1)  # 简化适应度计算

    def _crossover(self, parent1: List[Tuple[int, int]],
                   parent2: List[Tuple[int, int]]) -> List[Tuple[int, int]]:
        """路径交叉操作"""
        # 简单的单点交叉
        if len(parent1) < 3 or len(parent2) < 3:
            return parent1[:] if random.random() < 0.5 else parent2[:]

        # 找到两条路径的公共节点
        common_nodes = list(set(parent1) & set(parent2))

        if common_nodes and len(common_nodes) > 1:
            # 在公共节点处分割并重组
            common_node = random.choice(common_nodes[1:])  # 不选择起点
            idx1 = parent1.index(common_node)
            idx2 = parent2.index(common_node)

            child = parent1[:idx1] + parent2[idx2:]
        else:
            # 随机交叉点
            cut_point = random.randint(1, min(len(parent1), len(parent2)) - 1)
            child = parent1[:cut_point] + parent2[cut_point:]

        # 修复路径中的冲突（重复节点）
        fixed_path = []
        visited = set()

        for node in child:
            if node not in visited:
                fixed_path.append(node)
                visited.add(node)

        # 如果末尾不是终点，尝试修复路径，连接到终点
        if fixed_path and fixed_path[-1] != self.end_index:
            fixed_path = self._repair_path(fixed_path)

        return fixed_path

    def _mutate(self, path: List[Any]) -> List[Any]:
        """路径变异操作"""
        if len(path) < 3 or random.random() > self.mutation_rate:
            return path[:]

        mutated_path = path[:]

        # 随机选择变异方式
        mutation_type = random.choice(['remove', 'insert', 'swap'])

        if mutation_type == 'remove' and len(mutated_path) > 2:
            # 随机移除一个中间节点
            idx = random.randint(1, len(mutated_path) - 2)
            mutated_path.pop(idx)
        elif mutation_type == 'insert' and len(mutated_path) > 1:
            # 在随机位置插入一个新的邻近节点
            idx = random.randint(1, len(mutated_path) - 1)
            prev_node = mutated_path[idx - 1]

            # 获取相邻可通行节点
            neighbors = self._get_neighbors_indexes(prev_node, path)

            if neighbors:
                new_node = random.choice(neighbors)
                mutated_path.insert(idx, new_node)
        elif mutation_type == 'swap' and len(mutated_path) > 3:
            # 交换两个中间节点
            idx1 = random.randint(1, len(mutated_path) - 2)
            idx2 = random.randint(1, len(mutated_path) - 2)
            if idx1 != idx2:
                mutated_path[idx1], mutated_path[idx2] = mutated_path[idx2], mutated_path[idx1]

        return mutated_path

    def _repair_path(self, path: List[Any]) -> List[Any]:
        """尝试修复路径，使其到达终点"""
        if not path or path[-1] == self.end_index:
            return path

        current_index = path[-1]
        repaired_path = path[:]

        # 尝试从当前位置找到到终点的路径
        max_repair_steps = 5
        steps = 0

        while current_index != self.end_index and steps < max_repair_steps:
            # 选择最接近终点的邻居
            neighbors = self._get_neighbors_indexes(current_index, repaired_path)
            if not neighbors:
                break

            best_neighbor = min(neighbors,
                                key=lambda neighbor: h3.h3_distance(neighbor, self.end_index))

            repaired_path.append(best_neighbor)
            current_index = best_neighbor
            steps += 1

        return repaired_path

    # 执行遗传算法寻找路径
    def find_path(self) -> Optional[List[Any]]:
        # 记录开始时间
        start_time = time.time()
        # 初始化种群
        population = []
        # 按照种群大小生成一定的初始路径
        for _ in range(self.population_size):
            individual = self._generate_random_path()
            population.append(individual)
        best_path = None # 最佳路径
        best_fitness = 0 # 最佳适应度
        # 添加存储前n路径的列表
        top_paths = []  # 存储 (path, fitness, cost) 元组
        # 按照最大迭代次数进行迭代
        for generation in range(self.max_generations):
            # 计算适应度
            fitness_scores = []
            # 计算种群中每个个体的适应度，同时更新最佳适应度与最佳路径
            for individual in population:
                fitness = self._calculate_fitness(individual)
                fitness_scores.append(fitness)
                # 更新最佳路径
                if fitness > best_fitness:
                    best_fitness = fitness
                    best_path = individual[:]
                # 更新前n路径列表
                path_cost = self.calculate_path_cost(individual) if individual[-1] == self.end_index else float('inf')
                top_paths.append((individual[:], fitness, path_cost))
                # 按适应度排序并保留前n个
                top_paths.sort(key=lambda x: x[1], reverse=True)
                top_paths = top_paths[:self.top_paths_count]
            # 如果找到完美解则提前结束
            if best_path and best_path[-1] == self.end_index:
                print(f"在第 {generation + 1} 代找到解决方案")
                # print(f"最佳路径成本: {best_cost}")
                # break
            # 选择新一代个体
            new_population = []
            # 保留最佳个体（精英主义）
            elite_count = self.population_size // 10
            sorted_indices = np.argsort(fitness_scores)[::-1]
            for i in range(elite_count):
                idx = sorted_indices[i]
                new_population.append(population[idx][:])
            # 填充剩余个体
            while len(new_population) < self.population_size:
                # 轮盘赌选择两个父代
                parent1 = self._roulette_selection(population, fitness_scores)
                parent2 = self._roulette_selection(population, fitness_scores)
                # 交叉生成子代
                child = self._crossover(parent1, parent2)
                # 变异
                child = self._mutate(child)
                new_population.append(child)
            population = new_population
            # 输出进度
            if generation % 50 == 0:
                print(f"第 {generation} 代，当前最佳适应度: {best_fitness}")
        # 计算执行时间
        end_time = time.time()
        execution_time = end_time - start_time
        # 输出执行时间信息
        print(f"算法执行时间: {execution_time:.4f} 秒")
        # 输出前n路径信息
        print(f"\n适应度前{self.top_paths_count}的路径:")
        for i, (path, fitness, cost) in enumerate(top_paths):
            print(f"第{ i +1}名 - 适应度: {fitness:.6f}", end="")
            if path[-1] == self.end_index:
                print(f", 路径成本: {cost:.2f}, 路径: {path} (到达终点)")
            else:
                print(f", 路径: {path} (未到达终点)")
        # 保存前n路径以供可视化
        self.top_paths = top_paths
        return best_path if best_path and best_path[-1] == self.end_index else None

    @staticmethod
    def _roulette_selection(population: List[List[Any]],
                            fitness_scores: List[float]) -> List[Any]:
        """轮盘赌选择"""
        total_fitness = sum(fitness_scores)
        if total_fitness == 0:
            return random.choice(population)[:]

        pick = random.uniform(0, total_fitness)
        current = 0

        for i, fitness in enumerate(fitness_scores):
            current += fitness
            if current >= pick:
                return population[i][:]

        return population[-1][:]

if __name__ == '__main__':
    map = load_map('D:\MyFiles\Projects\pp-django\data\map_with_buildings.bin')
    print("地图加载完成")
    gaPathFinder = GeneticPathFinder(map, "8d30910f6b6c43f", "8d30910f47936bf")
    gaPathFinder.find_path()